package newcoder_exp.justPractise;

import java.util.Arrays;
import java.util.Random;

import org.junit.Test;

import utils.ArrayGenerator;

public class Nc88 {


   /* 
        有一个整数数组，请你根据**快速排序**的思路，找出数组中第K大的数。
        给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。
   */ 
    public class Solution {
        public int findKth(int[] a, int n, int K) {
            if (a == null || a.length == 0) return -1;
            return sort(a, K - 1, 0, a.length - 1);
        }

        public int sort(int[] nums, /* int n, */ int k, int lo, int hi) {
            if (lo <= hi) {
                int p = partion(nums, lo, hi);
                if (k == p) return nums[p];
                else if (p > k) {
                    return sort(nums, k, lo, p - 1);
                } else {
                    return sort(nums, k, p + 1, hi);
                }
            }
            return -1;
        }

        public int partion(int[] nums, int lo, int hi) {
            int s = nums[lo], i = lo, j = hi;
            while (i < j) {
                while (i < j && nums[j] <= s) j--;
                while (i < j && nums[i] >= s) i++;
                swap(nums, i, j);
            }
            swap(nums, i, lo);
            return i;
        }

        public void swap(int[] nums, int i, int j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }

    @Test
    public void test() {
        int[] nums = {1332802,1177178,1514891,871248,753214,123866,1615405,328656,1540395,968891,1884022,252932,1034406,1455178,821713,486232,860175,1896237,852300,566715,1285209,1845742,883142,259266,520911,1844960,218188,1528217,332380,261485,1111670,16920,1249664,1199799,1959818,1546744,1904944,51047,1176397,190970,48715,349690,673887,1648782,1010556,1165786,937247,986578,798663};
        // 5,3
        /* 
       ,49,24
        
        */
        Solution s = new Solution();
        for (int i = 0; i < 10; i++) {
            nums = ArrayGenerator.getArray(30, 10);
            int K = new Random().nextInt(10) + 1;
            int newArr[] = new int[10];
            System.arraycopy(nums, 0, newArr, 0, 10);
            int a = s.findKth(nums, 10, K);
            Arrays.sort(nums);
            int b = nums[10 - K];
            if (a != b) {
                System.out.println(Arrays.toString(newArr));
                System.out.println(Arrays.toString(nums));
                System.out.println(a);
                System.out.println(b);
                System.out.println(K);
                System.out.println("==========================");
            }
        }
        int res = s.findKth(nums, 49, 24);
        System.out.println(res);
    }

    @Test
    public void test2() {
        int[] nums = {1332802,1177178,1514891,871248,753214,123866,1615405,328656,1540395,968891,1884022,252932,1034406,1455178,821713,486232,860175,1896237,852300,566715,1285209,1845742,883142,259266,520911,1844960,218188,1528217,332380,261485,1111670,16920,1249664,1199799,1959818,1546744,1904944,51047,1176397,190970,48715,349690,673887,1648782,1010556,1165786,937247,986578,798663};
        // 5,3
        /* 
       ,49,24
        
        */
        Solution s = new Solution();
        nums = new int[]{28, 23, 26, 3, 8, 9, 11, 11, 14, 28};
    }
}
